//#define  _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//#include <vector>
//#include <cmath>
//#include <algorithm>
//using namespace std;
//
////
////
////int main()
////{
////	//int n = 0;
////	//cin >> n;
////	//vector<int> v(n, 0);
////	//for (int i = 0; i < n; i++)
////	//	cin >> v[i];
////	//for(int i = 0; i < 3; i++)
////	//	for (int j = 0; j < 3; j++)
////
////	//int a = 1;
////	//int b = 2;
////	//int c = 3;
////	//printf("a + b + c = %d\n", a + b + c);
////	//printf("a + b - c = %d\n", a + b - c);
////	//printf("a + b ^ c = %d\n", a + (b ^ c));
////
////	//printf("a - b + c = %d\n", a - b + c);
////	//printf("a - b - c = %d\n", a - b - c);
////	//printf("a - b ^ c = %d\n", a - (b ^ c));
////	//
////	//printf("a ^ b + c = %d\n", (a ^ b) + c);
////	//printf("a ^ b - c = %d\n", (a ^ b) - c);
////	//printf("a ^ b ^ c = %d\n", (a ^ b) ^ c);
////
////	int a = 1;
////	int b = 2;
////	int c = 3;
////	int d = 4;
////	printf("a + b + c + d = %d\n", a + b + c + d);
////	printf("a + b + c - d = %d\n", a + b + c - d);
////
////	printf("a + b - c + d = %d\n", a + b - c + d);
////	printf("a + b - c - d = %d\n", a + b - c - d);
////
////	printf("a - b + c + d = %d\n", a - b + c + d);
////	printf("a - b + c - d = %d\n", a - b + c - d);
////
////	printf("a - b - c + d = %d\n", a - b - c + d);
////	printf("a - b - c - d = %d\n", a - b - c - d); /// 8 * a
////
////
////	printf("a + b + c ^ d = %d\n", a + b + (c ^ d));
////	printf("a - b - c ^ d = %d\n", a - b - (c ^ d));
////
////	printf("a - b + c ^ d = %d\n", a - b + (c ^ d));
////	printf("a + b - c ^ d = %d\n", a + b - (c ^ d)); // 4 * a
////
////
////	printf("a + b ^ c + d = %d\n", a + (b ^ c) + d);
////	printf("a + b ^ c - d = %d\n", a + (b ^ c) - d);
////	printf("a - b ^ c + d = %d\n", a - (b ^ c) + d);
////	printf("a - b ^ c - d = %d\n", a - (b ^ c) - d); //4 * a
////
////	printf("a + b ^ c ^ d = %d\n", a + (b ^ c ^ d));
////	printf("a - b ^ c ^ d = %d\n", a - (b ^ c ^ d)); // 2 * a
////
////	printf("a ^ b + c + d = %d\n", (a ^ b) + c + d);
////	printf("a ^ b + c - d = %d\n", (a ^ b) + c - d);
////	printf("a ^ b + c ^ d = %d\n", (a ^ b) + (c ^ d));
////
////	printf("a ^ b - c + d = %d\n", (a ^ b) - c + d);
////	printf("a ^ b - c - d = %d\n", (a ^ b) - c - d);
////	printf("a ^ b - c ^ d = %d\n", (a ^ b) - (c ^ d)); // 6 * (a ^ b)
////
////	printf("a ^ b ^ c + d = %d\n", ((a ^ b) ^ c) + d); // 2 * (a ^ b ^ c)
////	printf("a ^ b ^ c - d = %d\n", (a ^ b ^ c) - d);
////
////	printf("a ^ b ^ c ^ d = %d\n", a ^ b ^ c ^ d);// a ^ b ^ c ^ d
////	return 0;
////}
////
//int main()
//{
//	int n = 0;
//	cin >> n;
//	vector<long long> v(n + 1, 0);
//	long long tmp = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> tmp;
//		v[i] = v[i - 1] ^ tmp;
//		v[i] %= 1000000007;
//	}
//	long long ret = 0;
//	for (int i = 1; i < n; i++)
//	{
//		tmp = 0;
//		tmp = v[i] * pow(3, n - i - 1) * 2;
//		tmp %= 1000000007;
//		ret += tmp;
//		ret %= 1000000007;
//	}
//	ret += v[n];
//	ret %= 1000000007;
//	cout << ret;
//	return 0;
//}
////
////int main()
////{
////	//cout << (1 ^ 2) << endl;
////	//cout << (1 ^ 2 ^ 3) << endl;
////	//cout << (1 ^ 2 ^ 3 ^ 4) << endl;
////	int n = 0;
////	cin >> n;
////	vector<long long> v(n);
////	for (int i = 0; i < n; i++)
////		cin >> v[i];
////
////	vector<long long> dict(n);
////	for (int i = 0; i < n; i++)
////		dict[i] = dict[i - 1] ^ v[i];
////
////
////
////	long long ret = 0;
////	long long tmp = 0;
////
////	tmp %= 1000000007;
////	ret += tmp;
////
////	for (int i = n - 1; i > 0; i--)
////	{
////		tmp = 0;
////		for (int j = 0; j < i; j++)
////			tmp ^= v[j];
////		tmp *= 2 * pow(3, (n - 1) - i);
////		tmp %= 1000000007;
////		ret += tmp;
////		ret %= 1000000007;
////	}
////	cout << ret;
////	return 0;
////}